public class Solution377 {
    /**
     * 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
     */
    int sum;

    public int combinationSum4(int[] nums, int target) {
        dps(nums, target);
        return sum;
    }

    private void dps(int[] nums, int target) {
        for (int num : nums) {
            if (target - num == 0) {
                sum++;
            }else if (target - num > 0) {
                dps(nums, target - num);
            }
        }
    }

    public int combinationSum4_2(int[] nums, int target) {
        if (nums.length == 0) return 0;
        int[] dp = new int[target +1];
        dp[0] = 1;
        for (int i = 1; i < target + 1; i++) {
            for (int num : nums) {
                if (i >= num){
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

}
